/**
 * 斐波那契数列是另一个可以用递归解决的问题。它是一个由 0、1、1、2、3、5、8、13、21、34 等数组成的序列。
 * 数 2 由 1 + 1 得到，数 3 由 1 + 2 得到，数 5 由 2 + 3 得到，以此类推。
 * 斐波那契数列的定义如下。
 * 位置 0 的斐波那契数是零。
 * 1 和 2 的斐波那契数是 1。
 * n（此处 n > 2）的斐波那契数是（n - 1）的斐波那契数加上（n - 2）的斐波那契数。
 */

// 迭代求斐波那契数
function fibonacciIterative(n) {
  if (n < 1) return 0;
  if (n <= 2) return 1;
  let FibNMinus2 = 0;
  let FibNMinus1 = 1;
  let fibN = 0;
  for (let i = 2; i <= n; i++) {
    fibN = FibNMinus2 + FibNMinus1;
    FibNMinus2 = FibNMinus1;
    FibNMinus1 = fibN;
  }
  return fibN;
}

// console.log(fibonacciIterative(42));

function fibonacci(n) {
  if (n === 0) return 0;
  if (n <= 2) return 1;
  return fibonacci(n - 1) + fibonacci(n - 2);
}
console.time('执行斐波拉契函数时间');
console.log(fibonacci(45));
console.timeEnd('执行斐波拉契函数时间');

function fibonacciMemoization(n) {
  const memo = [0, 1];
  const fibonacci = (n) => {
    if (memo[n] != null) return memo[n];
    return (memo[n] = fibonacci(n - 1) + fibonacci(n - 2));
  };
  return fibonacci(n);
}

console.time('执行记忆化斐波拉契函数时间');
console.log(fibonacciMemoization(45));
console.timeEnd('执行记忆化斐波拉契函数时间');
